
//42.接雨水
class Solution {
public:
    int trap(vector<int>& height) {
        //此题可以使用双指针进行实现，依旧移动柱子矮的一边，但是在每一次只是将一列进行注水
        //并且需要存储左右两边最长的柱子
        int left=0,right=height.size()-1;
        int left_max=0,right_max=0;
        int ret=0;
        while(left<right)
        {
            if(height[left]<height[right])
            {
                left_max=max(left_max,height[left]);
                ret+=left_max-height[left++];
            }
            else 
            {
                right_max=max(right_max,height[right]);
                ret+=right_max-height[right--];
            }
        }
        return ret;
    }
};